package com.lxm.algorithm.leetCode;

/**
 * Created by LXM on 2019/6/23.
 */
public class Fib {

    public int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public int fibLoop(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int pp = 1, p = 1;
        int t = 0;
        for (int i = 3; i <= n; i++) {
            t = pp + p;
            pp = p;
            p = t;
        }
        return t;
    }

    public static void main(String[] args) {
        Fib fib = new Fib();
        System.out.println(fib.fib(20));
        System.out.println(fib.fibLoop(20));
    }
}
